package com.klangner.utils;

import java.util.*;

// If the capacity has been reached, remove the "weakest link"
public class PriorityQueue extends LinkedList {
    public boolean add(Object element) {
        assert(maxCapacity_ >= size());// "Inconsistent PriorityQueue"

            // Don't let the PriorityQueue grow beyond maxCapacity_
        if (maxCapacity_ <= size()) {
            assert(size() > 0); // "Empty PriorityQueue"
            Object removed = removeFirst();
        }

        if (isEmpty()) {
            super.add(element);
            return true;
        } else {
            ListIterator it = listIterator();
            for (; it.hasNext();) {
                Object curInList = it.next();
                if (comparator_.compare(element, curInList) <= 0) {
                    it.previous();
                    it.add(element);
                    return true;
                }

                    // Our element is bigger than anything in the list, so we'll add it in the end.
                super.add(element);
            }
        }
        return true;
    }

    public PriorityQueue(int maxCapacity, Comparator comparator) {
            maxCapacity_ = maxCapacity;
            comparator_ = comparator;
        }

    private int maxCapacity_ = 0;
    private Comparator comparator_;
}
